package morris

import "fmt"

func MorrisPos(head *Node){
	cur := head
	var mostRight *Node

	for cur != nil {
		mostRight = cur.Left
		if mostRight != nil {
			for mostRight.Right != nil && mostRight.Right != cur {
				mostRight = mostRight.Right
			}
			if mostRight.Right == nil {
				mostRight.Right = cur
				cur = cur.Left
				continue
			} else {
				mostRight.Right = nil
				PrintEdge(cur.Left)
			}
		}
		cur = cur.Right
	}
	PrintEdge(head)
}

func PrintEdge(node *Node) {
	tail := ReverseNodeList(node)
	PrintNodeList(tail)
	ReverseNodeList(tail)
}

func ReverseNodeList(head *Node) *Node {
	var pre *Node
	var tem *Node
	for head != nil {
		tem = head.Right
		head.Right = pre
		pre = head
		head = tem
	}
	return pre
}

func PrintNodeList(head *Node) {
	for head != nil {
		fmt.Println(head.Val)
		head = head.Right
	}
}
